import java.util.*;
/**
 * 序列化二叉树
 * 
 * 描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 
n
≤
100
n≤100，树上每个节点的值满足 
0
≤
v
a
l
≤
150
0≤val≤150
要求：序列化和反序列化都是空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
n
)
O(n)
 */
public class 序列化二叉树 {
    
    public static void main(String[] args) {
        
        
    }

    private static String Serialize(TreeNode root) {
        return rSerialize(root, "");
    }

    private static String rSerialize(TreeNode root, String s) {
        if (root == null)
            s += "#!";
        else {
            s += root.val + "!";
            s = rSerialize(root.left, s);
            s = rSerialize(root.right, s);
        }
        return s;
    }

    TreeNode Deserialize(String str) {

        String[] nodes = str.split("!");    //将字符串划分成数组
        List<String> node_list = new LinkedList<>(Arrays.asList(nodes));
        return rDeserialize(node_list);
    }

    private static TreeNode rDeserialize(List<String> node_list) {
        //当前节点为空，则返回null
        if (node_list.get(0).equals("#") || node_list.get(0) == "#") {
            node_list.remove(0);
            return null;
        }
        //总是根据首位元素确定当前子树的根
        TreeNode root = new TreeNode(Integer.valueOf(node_list.get(0)));
        node_list.remove(0);
        root.left = rDeserialize(node_list);
        root.right = rDeserialize(node_list);
        //返回当前jiedian
        return root;
    }
}
